home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8103 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.1 KB
  1. Path: news1.cle.ab.com!usenet
  2. From: don.phillips@ab.com (Donald-Anthony C. Phillips)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: need psudeo code for binary search
  5. Date: Fri, 01 Mar 1996 19:14:52 GMT
  6. Organization: The Allen-Bradley Co., Inc
  7. Distribution: inet
  8. Message-ID: <4h77mu$qtb@news1.cle.ab.com>
  9. References: <Pine.SOL.3.91.960229154211.27358B-100000@obelix>
  10. NNTP-Posting-Host: abpc386.cle.ab.com
  11. X-Newsreader: Forte Free Agent 1.0.82
  12.  
  13. The binary search algorithm works as follows:
  14. 1) Remember the structure must already be sorted.
  15. 2) It works better as a recursive function
  16.  
  17.     
  18. BinarySearch(key,start,end)
  19.     find the middle element (current_position = (start + end) div 2)
  20.     if the key == array(current_position)
  21.         return(array(current_position))
  22.     else if the key < array(current_position) 
  23.         BinarySearch(key,start,current_position -1)
  24.     else if the key > current_position
  25.         BinarySearch(key,current_position + 1, end)
  26.     end
  27.  
  28. The real question is what is its order of magnitude O(n)????
  29. Donald-Anthony C. Phillips
  30. Programmer/Analyst
  31.  Rockwell  Automation
  32.        ---------------------------------------
  33.         Allen-Bradley
  34. don.phillips@ab.com
  35.  
  36.